package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

/**
 * <a href="https://leetcode.cn/problems/convert-bst-to-greater-tree/">把二叉搜索树转换为累加树 [中等]</a>
 * 等价于<a href="https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/submissions/">从二叉搜索树到更大和树 [中等]</a>
 * 二叉搜索树中序遍历就是从小到大的遍历（根据二叉搜索树定义），所以改成：右->中->左 的遍历方式就能够实现从大到小进行遍历。从大到小进行累加就是题解
 *
 * @author zhenzicheng
 * @date 2022-07-05 17:51
 */
public class ConvertBstToGreaterTree_538 {

  int curSum = 0; // 当前节点的累加值

  /*从最大的往小进行累加*/
  public TreeNode convertBST(TreeNode root) {
    if (root != null) {
      convertBST(root.right); // 一直往右找到最右边的叶子节点也即最大的元素

      root.val = root.val + curSum; // 计算新的累加和
      curSum = root.val; // 刷新累加和

      convertBST(root.left); // 往左子树遍历

      return root;
    }
    return null;
  }
}
